﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Gqq.Csharpindepth.DataStructure
{
    public class QuickSortClass
    {

        /// <summary>
        /// 快速排序
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="start"></param>
        /// <param name="end"></param>
        public static void QuikSort(int[] arr, int start, int end)
        {
            if (start >= end)
                return;
            int i = start, j = end;
            int pi = arr[i];
            while (i < j)
            {
                while (i < j && arr[j] >= pi) --j;
                //右移
                if (i < j && arr[j] < pi)
                {
                    var temp = arr[j];
                    arr[j] = pi;
                    arr[i] = temp;
                }
                //左移
                while (i < j && arr[i] <= pi) ++i;
                if (i < j && arr[i] > pi)
                {
                    var temp = arr[i];
                    arr[i] = pi;
                    arr[j] = temp;
                }
            }
            foreach (int i1 in arr)
            {
                Console.Write(i1 + "\t");
            }
            Console.WriteLine();
            QuikSort(arr, start, i - 1);
            QuikSort(arr, j + 1, end);
        }
    }
}
